package dp;

class 马在棋盘上的概率_688_重做版 {
    int[][] moves = new int[][]{{2,-1},{2,1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
    public double knightProbability(int n, int k, int row, int column) {
        double[][] dp0 = new double[n][n];
        // 初始状态
        dp0[row][column] = 1;
        for(;k > 0; k --) {  // 只使用一次 可以直接 -- 省下来一个局部变量的空间
            double[][] dp1 = new double[n][n];
            for(int r = 0 ; r < n ; r ++) {
                for(int c = 0 ; c < n ; c ++) {
                    for(int i = 0; i < moves.length; i++) {
                        int nextr = r + moves[i][0];
                        int nextc = c + moves[i][1];
                        if(nextc < 0 || nextc >= n || nextr < 0 || nextr >= n) continue; // 越界
                        dp1[nextr][nextc] += dp0[r][c] / 8.0; // // 每轮 概率累加 使用上一轮的结果来
                    }
                }
            }
            dp0 = dp1;
        }
        double res = 0;
        for(double[] i : dp0) {
            for(double j : i) {
                res += j;
            }
        }
        return res;
    }
}

public class 马在棋盘上的概率_688_3维dp数组 {
    /**
     * 3阶dp递推  3个for  几届就是几个for
     * dp[r][c][k] 表示第k次跳了之后  马在 r ，c 坐标的概率
     * dp边界   dp[row][column][0] = 1  即开始时  马在row  column的概率为1
     * dp状态转移方程  dp[nextR][nextC][k] = dp[nextR][nextC][k] + dp[r][c][k-1] / 8  每个点都有8种可能来源点  因此对应一个点概率要乘上 1/8
     * 注意  这里用2阶dp数组简化空间
     */
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dxy = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
        double[][] dp = new double[n][n];
        dp[row][column] = 1;
        // 一共k伦  每伦都是将数组从现有状态dp 修改为 dpTemp
        for (int kc = 0; kc < k; kc++) {
            double[][] dpTemp = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    for (int dxyc = 0; dxyc < 8; dxyc++) {
                        int nextr = r + dxy[dxyc][0];
                        int nextc = c + dxy[dxyc][1];
                        if (nextc >= 0 && nextc <= n - 1 && nextr >= 0 && nextr <= n - 1) {
                            // dpTemp[nextr][nextc] + dp[r][c] / 8;  而不是 dp[nextr][nextc] + dp[r][c] / 8;
                            // 因为自身不能往自身跳  只能把其他点跳过来的求和
                            dpTemp[nextr][nextc] = dpTemp[nextr][nextc] + dp[r][c] / 8;
                        }
                    }
                }
            }
            dp = dpTemp;
        }
        // 还在棋盘上的概率求和
        double res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
}
